package com.veal98.bactrack;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class LC17 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String digits = sc.nextLine();
        letterCombinations(digits);
    }

    // 数字对应的字符, 为了直接对应2-9，新增了两个无效的字符串""
    private static String[] arr = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    private static List<String> res = new ArrayList<>();

    public static List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return res;
        }

        // 标志位
        int start = 0;
        // 存储每个可能的组合
        StringBuilder track = new StringBuilder();
        backtrack(digits, track, start);
        return res;
    }

    /**
     * @param start 表示遍历到 digits 的第几个数字了
     */
    private static void backtrack(String digits, StringBuilder track, int start) {
        // 结束条件V
        if (start == digits.length()) {
            res.add(track.toString());
            // res.add(new String(track));
            return;
        }

        // 获取数字对应的字符集
        String str = arr[digits.charAt(start) - '0'];
        // 遍历选择列表
        for (int i = 0; i < str.length(); i ++) {
            // 剪枝(似乎没法做剪枝)

            // 做选择
            track.append(str.charAt(i));

            // 进入下一层解空间树
            backtrack(digits, track, start + 1);

            // 回溯
            track.deleteCharAt(track.length() - 1);
        }
    }

}
